package _剑指offer._回溯;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/generate-parentheses/
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 
 * @author Liu Huan
 */

public class _22_括号生成 {
	public static void main(String[] args) {
		List<String> ans = generateParenthesis(4);
		for (String str : ans) {
			System.out.print(str + "\t");
		}
	}
	
	private static List<String> ans = new ArrayList<>(); // 定义答案list
	private static StringBuilder cur = new StringBuilder();    // 存储当前括号对
	
	public static List<String> generateParenthesis(int n) {
		backtrack(0, 0, n);
		return ans;
	}
	
	/**
	 * 回溯法拼接括号
	 * 如何保证产生的括号是有效的：
	 * @param open  左括号的数量
	 * @param close 右括号的数量
	 * @param max   括号对的数量 n
	 */
	public static void backtrack(int open, int close, int max) {
		if (cur.length() == max * 2) {  //如果已经产生有效括号对，加入到答案list中
			ans.add(cur.toString());
			return;
		}
		if (open < max) {
			cur.append('(');
			backtrack(open + 1, close, max);
			cur.deleteCharAt(cur.length() - 1);
		}
		if (close < open) {
			cur.append(')');
			backtrack( open, close + 1, max);
			cur.deleteCharAt(cur.length() - 1);
		}
	}
}
